package 剑指offer;

import java.util.Arrays;

public class MergeSort {
    static int count;
    public static void mergeSort(int[] a, int low, int high) {
        if(low < high) {
            int mid = (low+high)/2;
            mergeSort(a, low, mid);
            mergeSort(a, mid+1, high);
            merge(a, low, mid, high);
        }
    }

    public static void merge(int[] a, int low, int mid, int high) {
        int[] b = new int[a.length];
        for(int m=low; m<=high; m++) {
            b[m] = a[m];
        }
        int i, j, k;
        for(i=low, j=mid+1, k=i; i<=mid&&j<=high; k++) {
            if(b[i] <= b[j]) {
                a[k] = b[i++];
            } else {
                a[k] = b[j++];
                count+=(mid-i+1);
            }
        }
        while (i<=mid) {
            a[k++] = b[i++];
        }
        while (j<=high) {
            a[k++] = b[j++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,0};
        mergeSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
        System.out.println(count);
    }
}
